package com.leetcode.算法策略相关.回溯;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/3/31
 * @description: 90. 子集 II
 * https://leetcode-cn.com/problems/subsets-ii/
 * 这种求列举集合的问题，用回溯是非常适合的。
 */
public class B_90_子集II {

static B_90_子集II action =new	B_90_子集II();

	public static void main(String[] args) {
//test1();
		test2();
//		test3();
	}

	static void test1(){
		//[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
		int[] nums = new int[]{1,2,2};
		List<List<Integer>> res = action.subsetsWithDupByBackTrack(nums);
		System.out.println("res = " + res);
	}

	static void test2(){
		//[[],[0],[0,1],[0,1,4],[0,4],[1],[1,4],[4]]
		//8
		int[] nums = new int[]{4,1,0};
		List<List<Integer>> res = action.subsetsWithDupByBackTrack(nums);
		System.out.println("res = " + res);
	}

	static void test3(){
		//
		int[] nums=new int[]{2,1,2,1,3};
		List<List<Integer>> res = action.subsetsWithDupByBackTrack(nums);
		System.out.println("res = " + res);
	}




	/**
	 * 对于回溯时形成的 list ，要生成一个副本放入 res ，想不到任何办法能够减少他的时间复杂度。
	 * 只能老老实实遍历。
	 * --
	 * 直接将 linkedList clear() 是有问题的。
	 * eg.(1,1,2,2,3) 中 (1,1,2,3) 的情况
	 * @param nums
	 * @return
	 */
	public List<List<Integer>> subsetsWithDupFail(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		res.add(new ArrayList<>());
		Arrays.sort(nums);
		//做一个 HashSet 的集合，存储每个 list 的哈希值，解决重复的问题
		//【hashCode 的生成问题】，如果自己写不太好办，应该有API封装好的。
		//用 String 应该可以，Integer,hashCode 直接返回了本身
		HashSet<String> set = new HashSet<>();
		int len = nums.length;
		LinkedList<Integer> linkedList = new LinkedList<>();

		int begin = 0, endIndex = len - 1;
		while (begin < len) {
			linkedList.add(begin);
			putRes(linkedList, res, nums, set);
			int interval = 1;
			for (int i = begin + interval; i < len; i++) {
				linkedList.add(i);
				putRes(linkedList, res, nums, set);
				if (i == endIndex) {
					linkedList.clear();
					linkedList.add(begin);
					i = begin + interval++;
				}
			}
			begin++;
			linkedList.clear();
		}
		return res;
	}


	//region	定义全局变量
	/**
	 * 记录 list 的 hash 集合
	 */
	HashSet<String> set = new HashSet<>();
	/**
	 * nums 的长度
	 */
	int len=0;
	/**
	 * 临时链表，用于存储回溯过程中的元素
	 */
	LinkedList<Integer> linkedList = new LinkedList<>();

	//endregion

	/**
	 * 通过回溯（回溯还是用递归比较好写，不然就有好几个地方都需要判断了）
	 * --
	 * 进一步还可以通过记忆化搜索进行优化！
	 * @param nums
	 * @return
	 */
	public List<List<Integer>> subsetsWithDupByBackTrack(int[] nums){
		List<List<Integer>> res = new ArrayList<>();
		res.add(new ArrayList<>());
		Arrays.sort(nums);
		len = nums.length;
		int begin = 0, endIndex = len - 1;
		for (int i = 0; i < len; i++) {
			linkedList.addLast(i);
			putRes(res, nums);
			backTrack(i+1, res, nums);

			linkedList.removeLast();
		}

		return res;
	}

	private void backTrack(int index, List<List<Integer>> res, int[] nums) {
		for (int i = index; i < len; i++) {
			linkedList.addLast(i);
			putRes(res, nums);
			backTrack(i+1, res, nums);

			//backtrack
			linkedList.removeLast();
		}
	}


	/**
	 * 有了上面的过程之后，就容易想到使用记忆化搜索进行优化！
	 * 定义 dp[i,j] 为 从 i 到 j 之间的所有的子串。
	 * 那么最后的结果就是 dp[0,len-1]
	 * @param nums
	 * @return
	 */
	public List<List<Integer>> subsetsWithDupByDP(int[] nums){
		List<List<Integer>> res = new ArrayList<>();
		res.add(new ArrayList<>());
		Arrays.sort(nums);
		len = nums.length;
		return null;
	}

	private void putRes(LinkedList<Integer> linkedList, List<List<Integer>> res, int[] nums, HashSet<String> set) {
		LinkedList<Integer> list = new LinkedList<>();
		StringBuilder sb=new StringBuilder();
		Iterator<Integer> iterator = linkedList.iterator();
		while (iterator.hasNext()) {
			Integer next = iterator.next();
			sb.append(nums[next]);
			list.add(nums[next]);
		}
		String hashCode=sb.toString();
		//遍历完毕
		if (!set.contains(hashCode)) {
			set.add(hashCode);
			res.add(list);
		}
	}

	private void putRes(List<List<Integer>> res, int[] nums) {
		LinkedList<Integer> list = new LinkedList<>();
		StringBuilder sb=new StringBuilder();
		Iterator<Integer> iterator = linkedList.iterator();
		while (iterator.hasNext()) {
			Integer next = iterator.next();
			sb.append(nums[next]);
			list.add(nums[next]);
		}
		String hashCode=sb.toString();
		//遍历完毕
		if (!set.contains(hashCode)) {
			set.add(hashCode);
			res.add(list);
		}
	}

}
